Various types of content addressable storage systems are known. Some content addressable storage systems allow data pages of one or more logical storage volumes to be accessed using content-based signatures that are computed from content of respective ones of the data pages. Such content addressable storage system arrangements facilitate implementation of deduplication and compression. For example, the storage system need only maintain a single copy of a given data page even though that same data page may be part of multiple logical storage volumes. Although these and other content addressable storage systems typically provide a high level of storage efficiency through deduplication and compression, problems can arise when there is a loss of metadata that maps a logical storage space to a physical storage space in the content addressable storage system. Conventional log-based approaches typically used to support failure recovery in these and other situations can be limited in terms of their history, coverage and capacity and as a result often do not support a sufficiently high probability of recovery success.